package in.hitmedia.test.recursion;

import java.util.HashSet;
import java.util.Set;

public class KnapSack 
{

	
	Set<Integer> optimalsolution = new HashSet<Integer>();
	private int max = 0;
	private int maxValue=0;
	private Item[] items;
	
	public KnapSack(final int max, final Item[] items)
	{
		this.max = max;
		this.items = items;
	}
	
	public void run(Set<Integer> s, int i, int totalWeight, int totalVal)
	{
		if ((totalWeight + items[i].getWeight()) <= max)
		{
			s.add(new Integer(i));
			if ( i < items.length-1)
			{
				run (s, i+1, totalWeight + items[i].getWeight(), totalVal);
			}
			else
			{
				if (totalVal > maxValue)
				{
					maxValue = totalVal;
					optimalsolution.clear();
					optimalsolution.addAll(s);
				}
			}
			s.remove(new Integer(i));
		}
		
		int excludedVal = totalVal - items[i].getValue();
		if ( excludedVal > maxValue)
		{
			if ( i < items.length -1)
			{
				run (s, i+1, totalWeight, excludedVal);
			}
			else
			{
				maxValue = excludedVal;
				optimalsolution.clear();
				optimalsolution.addAll(s);
			}
		}
		
	}
			
	
	public static void main(String args[])
	{
		Item item[] = new Item[3];
		item[0] = new Item(10, 18);
		item[1] = new Item(11, 20);
		item[2] = new Item(12, 17);
		//item[3] = new Item(13, 19);
		//item[4] = new Item(14, 25);
		//item[5] = new Item(15, 21);
		//item[6] = new Item(16, 27);
		//item[7] = new Item(17, 23);
		//item[8] = new Item(18, 25);
		//item[9] = new Item(19, 24);
		
		int totalValue = 0;
		for (int i=0; i < item.length; ++i)
		{
			totalValue+=item[i].getValue();
		}
		
		
		KnapSack ks = new KnapSack(12, item);
		ks.run(new HashSet<Integer>(), 0, 0, totalValue);
		
		System.out.println(ks.optimalsolution);
	}
}
